/*
 * @lc app=leetcode.cn id=1028 lang=typescript
 *
 * [1028] 从先序遍历还原二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function recoverFromPreorder(traversal: string): TreeNode | null {
  // 栈
  const n = traversal.length;
  const stk = [];
  let i = 0;
  // 树的深度，也就是"-"字符的数量
  let deep = 0;
  // 将数字字符转换为数字
  let num = 0;
  let node: TreeNode;

  while (i < n) {
    deep = num = 0;
    // 当前节点的深度
    while (traversal[i] == '-' && i < n) {
      i++;
      deep++;
    }
    // 当前节点的值
    while (traversal[i] !== '-' && i < n) {
      num = num * 10 + Number(traversal[i]);
      i++;
    }

    // 栈中元素数量大于深度，就将栈顶弹出，直到匹配深度
    while (stk.length > deep) {
      stk.pop();
    }
    node = new TreeNode(num);
    // 将当前节点挂载到栈顶的左右子节点上
    if (stk.length > 0) {
      const top = stk[stk.length - 1];
      if (top.left === null) {
        top.left = node;
      } else {
        top.right = node;
      }
    }
    stk.push(node);
  }

  // 返回栈底节点
  return stk[0];
}
// @lc code=end
